home *** CD-ROM | disk | FTP | other *** search
/ 500 MB Nyheder Direkte fra Internet 2 / 500 MB nyheder direkte fra internet CD 2.iso / start / data / text / ziplib-3.txt < prev   
Text File  |  1995-03-08  |  8KB  |  232 lines
  1.  
  2.           'ZIPLIB' COMPRESSED DATA FORMAT SPECIFICATION
  3.                 draft #3
  4.                 March 7, 1995
  5.  
  6.             Copyright (C) 1995 L. Peter Deutsch and Jean-loup Gailly
  7.  
  8.     Permission is granted to copy and distribute this document for
  9.     any purpose and without charge, provided that it is copied as a
  10.     whole (including the copyright notice and this notice) and with
  11.     no changes.
  12.  
  13. 1. Introduction
  14.  
  15. 1.1 Purpose
  16.  
  17. The purpose of this specification is to define a lossless compressed data
  18. format that:
  19.  
  20.     (a) Is independent of CPU type, operating system, file system, and
  21. character set, and hence can be used for interchange;
  22.  
  23.     (b) Can be produced or consumed, even for an arbitrarily long
  24. sequentially presented input data stream, using only an a priori bounded
  25. amount of intermediate storage, and hence can be used in data communications
  26. or similar structures such as Unix filters;
  27.  
  28.     (c) Can use a number of different compression methods;
  29.  
  30.     (d) Can be implemented readily in a manner not covered by patents,
  31. and hence can be practiced freely.
  32.  
  33. The data format defined by this specification does not attempt to
  34. allow random access to compressed data.
  35.  
  36.  
  37. 1.2 Intended audience
  38.  
  39. This specification is intended for use by implementors of software to
  40. compress data into ziplib format and/or decompress data from ziplib format.
  41.  
  42. The text of the specification assumes a basic background in programming at
  43. the level of bits and other primitive data representations.
  44.  
  45. 1.3 Scope
  46.  
  47. The specification specifies a compressed data format, to be used for
  48. in-memory compression of a sequence of arbitrary octets.
  49.  
  50. 1.4 Compliance
  51.  
  52. Unless otherwise indicated below, a compliant decompressor must be able to
  53. accept and decompress any data set that conforms to all the specifications
  54. presented here; a compliant compressor must produce data sets that conform
  55. to all the specifications presented here.
  56.  
  57. 1.4 Related standards
  58.  
  59. None.
  60.  
  61. 1.5 Other related publications
  62.  
  63. Deutsch, L.P.,"'Gzip' Compressed Data Format Specification".  Drafts
  64. being circulated.
  65.  
  66. Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".  Drafts
  67. being circulated.
  68.  
  69. Thomas Boutell, "PNG (Portable Network Graphics) specification".
  70.  
  71. Fletcher, J. G., "An Arithmetic Checksum for Serial Transmissions," IEEE  
  72. Transactions on Communications, Vol. COM-30, No. 1, January 1982, pp.  
  73. 247-252.
  74.  
  75. ITU-T Recommendation X.224, Annex D, "Checksum Algorithms," November,  
  76. 1993, pp. 144, 145. (Available from gopher://info.itu.ch). ITU-T X.244 is
  77. also the same as ISO 8073.
  78.  
  79.  
  80. 1.6 Definitions of terms and conventions used
  81.  
  82. octet: 8 bits stored or transmitted as a unit (same as a byte on most
  83. machines).  See section 3.1 below for the numbering of bits within an
  84. octet.
  85.  
  86.  
  87. 2. Detailed specification.
  88.  
  89. 2.1 Overall conventions.
  90.  
  91. In the diagrams below, a box like this:
  92.  
  93.     +---+
  94.     |   | <-- the vertical bars might be missing
  95.     +---+
  96.  
  97. represents one octet; a box like this:
  98.  
  99.     +==============+
  100.     |              |
  101.     +==============+
  102.  
  103. represents a variable number of octets.
  104.  
  105. Octets stored within a computer do not have a 'bit order', since they are
  106. always treated as a unit.  However, an octet considered as an integer
  107. between 0 and 255 does have a most- and least-significant bit, and since we
  108. write numbers with the most-significant digit on the left, we also write
  109. octets with the most-significant bit on the left.  In the diagrams below, we
  110. number the bits of an octet so that bit 0 is the least-significant bit,
  111. i.e., the bits are numbered:
  112.  
  113.     +--------+
  114.     |76543210|
  115.     +--------+
  116.  
  117. Within a computer, a number may occupy multiple octets.  All multi-octet
  118. numbers in the format described here are stored with the MOST-significant
  119. octet first (at the lower memory address).  For example, the decimal number
  120. 520 is stored as:
  121.  
  122.         0         1
  123.     +--------+--------+
  124.     |00000010|00001000|
  125.     +--------+--------+
  126.      ^      ^
  127.      |      |
  128.      |      + less significant octet = 8
  129.      + more significant octet = 2 x 256
  130.  
  131. 2.2 Data format.
  132.  
  133. The data have the following structure:
  134.  
  135.       0   1  
  136.     +---+---+=====================+---+---+---+---+
  137.     |CMF|FLG|...compressed data...|    ADLER32    |
  138.     +---+---+=====================+---+---+---+---+
  139.  
  140. CMF (Compression Method and flags)
  141.         This octet is divided into a 4-bit compression method and a 4-bit
  142.         information field depending on the compression method.
  143.                 bits 0 to 3  CM     Compression method
  144.                 bits 4 to 7  CINFO  Compression info
  145.   CM (Compression method)
  146.     This identifies the compression method used in the file. CM = 8
  147.     denotes the 'deflate' compression method with a window size up to 32K.
  148.     This is the method used by gzip; it is documented elsewhere.
  149.   CINFO (Compression info)
  150.         For CM = 8, CINFO is the base-2 logarithm of the LZ77 window size,
  151.         minus eight (CINFO=7 indicates a 32K window size). Values of CINFO
  152.         above 7 are not allowed in this version of the specification.
  153.         CINFO is not defined in this specification for CM not equal to 8.
  154.  
  155. FLG (FLaGs)
  156.     This flag octet is divided as follows:
  157.  
  158.         bits 0 to 4  FCHECK  (check bits for CMF and FLG)
  159.         bit  5       reserved, must be zero
  160.         bits 6 to 7  FLEVEL  (compression level)
  161.  
  162.   The FCHECK value must be such that CMF and FLG, when viewed as a 16-bit
  163.   unsigned integer stored in MSB order (CMF*256 + FLG), is a multiple of 31.
  164.  
  165.   FLEVEL (Compression level)
  166.     These flags are available for use by specific compression methods.
  167.     The 'deflate' method (CM = 8) sets these flags as follows:
  168.     0 - compressor used fastest algorithm
  169.     1 - compressor used fast algorithm
  170.     2 - compressor used default algorithm
  171.         3 - compressor used maximum compression, slowest algorithm
  172.      The information in FLEVEL is not needed for decompression; it is there
  173.      to indicate if recompression might be worthwhile.
  174.  
  175. ADLER32 (Adler-32 cheksum)
  176.     This contains a checksum value of the uncompressed data
  177. computed according to Adler-32 algorithm. This algorithm is a 32-bit
  178. extension and improvement of the Fletcher algorithm, used in the
  179. ITU-T X.224 / ISO 8073 standard.
  180.  
  181. Adler-32 is composed of two sums accumulated per octet: s1 is the sum
  182. of all octets, s2 is the sum of all s1 values. Both sums are done
  183. modulo 65521. s1 is initialized to 1, s2 to zero.  The Adler-32
  184. checksum is stored as s2*65536 + s1 in most-significant-octet first
  185. (network) order.
  186.  
  187.  
  188. 3. Appendix: Rationale
  189.  
  190. The Adler-32 algorithm is much faster than the CRC32 algorithm yet
  191. still provides an extremely low probability of undetected errors.
  192.  
  193. The modulo on unsigned long accumulators can be delayed for 5552 octets, so
  194. the modulo operation time is negligible.  If the octets are a, b, c, the
  195. second sum is 3a + 2b + c + 3, and so is position and order sensitive,
  196. unlike the first sum, which is just a checksum.  That 65521 is prime is
  197. important to avoid a possible large class of two-octet errors that leave
  198. the check unchanged.  (The Fletcher checksum uses 255, which is not prime
  199. and which also makes the Fletcher check insensitive to single octet changes
  200. 0 <-> 255.)
  201.  
  202. The sum s1 is initialized to 1 instead of zero to make the length of the
  203. sequence part of s2, so that the length does not have to be checked
  204. separately. (Any sequence of zeroes has a Fletcher checksum of zero.)
  205.  
  206.  
  207. The following C code computes the Adler-32 checksum of a data buffer:
  208.  
  209. #define BASE 65521 /* largest prime smaller than 65536 */
  210. #define NMAX 5552
  211. /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
  212.  
  213. unsigned long adler32(unsigned char *b, int n)
  214. {
  215.   unsigned char *p = b;
  216.   unsigned long s1 = 1;
  217.   unsigned long s2 = 0;
  218.   int k;
  219.  
  220.   while (n > 0) {
  221.     k = n < NMAX ? n : NMAX;
  222.     n -= k;
  223.     do {                        /* could unroll loop some for speed */
  224.       s1 += *p++;
  225.       s2 += s1;
  226.     } while (--k);
  227.     s1 %= BASE;
  228.     s2 %= BASE;
  229.   }
  230.   return (s2 << 16) | s1;
  231. }
  232.